package com.itzmn.java.javase.collections;

import com.itzmn.java.javase.collections.interfaces.QiYeDeque;

import java.util.NoSuchElementException;

/**
 * @Author: 张梦楠
 * @Date: 2018/12/6 15:58
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description:
 */
public class QiYeLinkedList<T> implements QiYeDeque<T> {

    private int size;
    private Node<T> first;
    private Node<T> last;

    public QiYeLinkedList(){

    }

    void linkFirst(T e){

        Node<T> f = this.first;
        Node<T> tNode = new Node<>(null, e, f);

        this.first = tNode;

        if (f == null){
            // 第一次插入数据
            last = tNode;
        }else {
            // 不是第一次，则将以前的首节点的前驱设为现在的首节点
            f.prev = first;
        }
        size++;

    }
    void linkLast(T e){

        Node<T> l = this.last;

        Node<T> tNode = new Node<>(l, e, null);

        last = tNode;

        if (l == null){
            // 如果是第一次添加，将头也设为当前节点
            first = tNode;
        }else {
            // 如果不是，将以前的尾节点的后序节点设为当前节点
            l.next = tNode;
        }

        size++;

    }

    T unlinkFirst(Node<T> e){

        T item = e.item;

        Node<T> next = e.next;
        first = next;

        e.item = null;
        e.next = null;
        if (next == null){
            last = null;
        }else {
            first.prev = null;
        }
        size--;

        return item;
    }
    T unlinkLast(Node<T> e){

        T item = e.item;
        Node<T> prev = e.prev;
        last = prev;
        e.item = null;
        e.prev = null;
        if (prev == null){
            first = null;
        }else {
            last.next = null;
        }
        size --;
        return item;
    }
    @Override
    public T getFirst() {
        Node<T> first = this.first;
        if (first == null){
            throw new NoSuchElementException();
        }
        return first.item;
    }

    @Override
    public T getLast() {
        Node<T> last = this.last;
        if (last == null){
            throw new NoSuchElementException();
        }
        return last.item;
    }

    @Override
    public T peekFirst() {

        return first == null ? null:first.item;
    }

    @Override
    public T peekLast() {
        return last == null ? null:last.item;
    }

    @Override
    public void addFirst(T e) {

        linkFirst(e);


    }

    @Override
    public void addLast(T e) {

        linkLast(e);
    }

    @Override
    public boolean offerFirst(T e) {
        addFirst(e);
        return true;
    }

    @Override
    public boolean offerLast(T e) {
        addLast(e);
        return true;
    }

    @Override
    public T removeFist() {
        Node<T> f = this.first;
        if (f == null){
            throw new NoSuchElementException();
        }

        return unlinkFirst(first);
    }

    @Override
    public T removeLast() {
        Node<T> f = this.last;
        if (f == null){
            throw new NoSuchElementException();
        }

        return unlinkFirst(last);
    }

    @Override
    public T pollFirst() {

        Node<T> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

    @Override
    public T pollLast() {
        Node<T> l = last;
        return (l == null) ? null : unlinkLast(l);
    }

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}
